class Solution(object):
    def threeSumClosest(self, nums, target):  # O(n^2)
        """
        :type nums: List[int], length >= 3
        :type target: int
        :rtype: int
        """
        if len(nums) < 3: return 0
        nums.sort()
        res = sum(nums[:3])
        margin = abs(target - res)
        for i, n in enumerate(nums):
            l = i + 1
            r = len(nums) - 1
            while l < r:
                val = n + nums[l] + nums[r]
                if abs(target - val) < margin:
                    margin = abs(target - val)
                    res = val
                if val > target:
                    r -= 1
                elif val < target:
                    l += 1
                else:
                    return target
        return res


if __name__ == "__main__":
    soln = Solution()
    print(soln.threeSumClosest([], 3))
    print(soln.threeSumClosest([1], 3))
    print(soln.threeSumClosest([1,2], 3))
    print(soln.threeSumClosest([-1,2,1,-4], 1))
    print(soln.threeSumClosest([-1,0,1,2,-1,-4,4,1], 5))
    print(soln.threeSumClosest([-1,0,1,2,-1,-4,4,7], 35))
    print(soln.threeSumClosest([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6], 8))
